package com.atguigu.practice;

public class ListPartition {
    public static ListNode partition(ListNode head,int x){
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode lessHead=new ListNode(0);
        ListNode greatHead=new ListNode(0);
        ListNode node1=lessHead;
        ListNode node2=greatHead;
        ListNode cur=head;
        //将小于x的节点尾插入lessHead,大于x的节点尾插入greatHead
        while(cur!=null){
            if(cur.val<x){
                node1.next=cur;
                node1=cur;
            }else{
                node2.next=cur;
                node2=cur;
            }
            cur=cur.next;
        }
        //将greatHead拼接在lessHead之后形成一个链表
        node1.next=greatHead.next;
        node2.next=null;
        return lessHead.next;
    }

    public static void main(String[] args) {

    }
}
